package code.cando;

import java.util.HashMap;
import java.util.HashSet;

/**
 * author : yeswater
 * date : 2023/12/4
 * 
 *      给定一个字符串s,找出一个不含重复字符的 最长子串的长度
 */

public class T003 {
    public static void main(String[] args) {
        // String str = "dvdf";
        String str = "pwwkew";
        System.out.println(lengthOfLongestSubstring(str));
    }

    public static int lengthOfLongestSubstring(String s) {
        int longest = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                longest = Math.max(longest, map.size());
                // 有重复的从前一个重复的往后 put
                int index = map.get(s.charAt(i)) + 1;
                map.clear();
                for (int j = index; j < i; j++) {
                    map.put(s.charAt(j), j);
                }
            }
            map.put(s.charAt(i), i);
        }
        return Math.max(longest, map.size());
    }

    // 左右指针 i,j 节省了 clear 和重复 put 的时间
    public static int lengthOfLongestSubstring2(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int i = -1;  // 左指针
        int res = 0; // 结果
        int len = s.length();
        for (int j = 0; j < len; j++) { // 右指针
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(i, map.get(s.charAt(j)));
            }
            map.put(s.charAt(j), j);
            res = Math.max(j - i, res);
        }
        return res;
    }
}
